-- Copyright (c) 2010, bkil.hu
-- This program is free software and can be distributed under the terms of
-- the GNU General Public License v2,
-- see COPYING for detailed licensing terms.
-- created on 2010-06-07 16:12
-- elementwise processing, simple 2-to-1 version

import Data.Maybe(catMaybes)

data KV key value = KV key value deriving Show

instance Eq k => Eq (KV k v) where
    (==) (KV k1 _) (KV k2 _) = k1==k2

instance Ord k => Ord (KV k v) where
    (<=) (KV k1 _) (KV k2 _) = k1<=k2

type OKVL key value = [KV key value]
type MKV k v = Maybe (KV k v)
type KV11 k v = KV k v -> MKV k v
type KV21 k v = KV k v -> KV k v -> MKV k v

ep_2_1 :: Ord k => KV11 k v -> KV11 k v -> KV21 k v -> OKVL k v -> OKVL k v -> OKVL k v
ep_2_1 f1 f2 f12 xs ys = catMaybes $ f [] xs ys where
 f zs (x:xs) (y:ys) =
  case compare x y of
   LT -> f (f1 x:zs)    xs     (y:ys)
   GT -> f (f2 y:zs)    (x:xs) ys
   EQ -> f (f12 x y:zs) xs     ys
 f zs xr yr = reverse zs ++ map f1 xr ++ map f2 yr

ep_update xs ys = ep_2_1 Just Just (\_ y->Just y) xs ys

main = print $ ep_update db patch where
 db    = [KV 1 9, KV 3 8, KV 4 7, KV 5 6, KV 7 5]
 patch = [KV 2 5, KV 4 4, KV 6 3]
